package O4_Insertion_Sort;

import util.SortTestHelper;

import java.util.Arrays;

/**
 * Created by Choisaaaa on 2018/6/19.
 * 优化插入排序
 * 插入排序可以提前终止内存循环
 */

public class InsertionSort_Advance {
    public static void sort(Comparable[] arr){
        int n = arr.length;
        for (int i = 1; i < n ; i++){
            Comparable e = arr[i];//保存待比较元素的副本
            int j = i;
            for (;j > 0 && arr[j-1].compareTo(arr[j]) > 0 ;j--){
                arr[j] = arr[j-1];
            }
            arr[j] = e;
        }
    }

    public static void main(String[] args) {
        int N = 20000;
        Integer[] arr = SortTestHelper.generateRandomArray(N,0,10000);
        SortTestHelper.testSort("O4_Insertion_Sort.InsertionSort",arr);

        Integer[] arr2 = Arrays.copyOf(arr, arr.length);
        SortTestHelper.testSort("O4_Insertion_Sort.InsertionSort_Advance",arr2);
    }
}
